<?php
set_time_limit(0);
ini_set('error_reporting', E_ALL);
include '../Homework4/HeapSort.php';

//$array = generateRandomSortedArray();
//insertArrayIntoFile('arraySort.txt', $array);
//repetitiveSearch();
//performSearchInTimeInterval();

//compareCountingSort();

//var_dump(countingSort(array(4,3,4,5,1,46,7,8)));
//var_dump(radixSort(array(23,242425,25252525,52525,112,99,1,2)));
compareRadixSort();

function compareRadixSort() {
	$file = fopen('log10000v1.txt', 'w+'); // Save into .csv to open Excel
	
	for ($i = 0; $i < 100;$i++) {
		echo memory_get_usage() . '<br>';
		$array = generateRandomArray(10000, 4095, false);
		$start = microtime(true);
		
		$result = countingSort($array);
		
		$end = microtime(true);
		$countingSortTime = ($end-$start);
		$start = microtime(true);
		$result = radixSort($array);
		$end = microtime(true);
		$radixSortTime = ($end-$start);
		
		$arrayCopy = $array;
		$start = microtime(true);
		sort($arrayCopy); // Quicksort
		$end = microtime(true);
		$nativeSortTime = ($end-$start);

		$start = microtime(true);
		echo memory_get_usage() . '<br>';
		$result = heapSort($array);
		$end = microtime(true);
		$heapSortTime = ($end-$start);
		echo memory_get_usage() . '-<br>';
		die('x');
		fwrite($file,$nativeSortTime . "\t" . $countingSortTime . "\t" . $radixSortTime . "\t" . $heapSortTime . PHP_EOL);
	}

	
	fclose($file);
}

function radixSort(array $array) {
	$bits = PHP_INT_SIZE * 8;
	$lsb = 1;
	
	for ($i = 0; $i < $bits; $i++) {
		$buckets = array(
			0 => array(),
			1 => array()
		);
		
		foreach ($array as $element) {
			if ($element & $lsb) {
				$buckets[1][] = $element;
			} else {
				$buckets[0][] = $element;
			}
		}
		
		$array = array();
		foreach ($buckets as $bucket) {
			foreach ($bucket as $element) {
				$array[] = $element;
			}
		}
		
		$lsb = $lsb << 1;
	}
	
	return $array;
}


function compareCountingSort() {
	
	
	for ($i = 0; $i < 100; $i++) {
		
		echo memory_get_usage() . '<br>';
		$array = generateRandomArray(1000, 4095, false);
		$start = microtime(true);
		$result = countingSort($array);
		$end = microtime(true);
		echo memory_get_usage() . '<br>';
		$countingSortTime = ($end-$start);
		
		$arrayCopy = $array;
		$start = microtime(true);
		sort($arrayCopy); // Quicksort
		$end = microtime(true);
		$nativeSortTime = ($end-$start);
		
	//	echo $countingSortTime . "\t" . $nativeSortTime . '<br>';
	}

	
	
}
function countingSort(array $array) {
	$k = max($array);
	$n = count($array)-1;
	$aux = array();
	$result = array();
	
	for ($i = 1; $i <= $k; $i++) {
		$aux[$i] = 0;
	}
	foreach ($array as $i => $element) {
		$aux[$element] = $aux[$element]+1;
		// Creating array with predefined indexes, otherwise
		// Otherwise indexes are in that order how we insert them
		$result[$i+1] = 0;			
	}

	for ($i = 2; $i <= $k; $i++) {
		$aux[$i] = $aux[$i] + $aux[$i-1];
	}

	for($i=$n; $i >= 0; $i--) {
		$result[$aux[$array[$i]]] = $array[$i];
		$aux[$array[$i]] = $aux[$array[$i]]-1;
	}
	unset($array);
	unset($aux);
	unset($result);
	//return $result;
}


function test() {
	$array = readArrayFromFile('arraySort.txt');
	$low = 0;
	$high = count($array)-1;	
	$value = 3909;
	
	echo 'Recursive binary search: ';
	echo recBinarySearch($array, $value, $low, $high) . '<br>';
	
	echo 'Iterative binary search: ';
	echo iterBinarySearch($array, $value) . '<br>';
}

/**
 * $interval in seconds
 * @param int $interval
 */
function performSearchInTimeInterval($interval = 1) {
	$count = 0;
	$timeElapsed = 0;
	
	while ($timeElapsed < $interval) {
		$array = generateRandomArray();
		$low = 0;
		$high = count($array)-1;
		$value = mt_rand(0, 4095);
		$start = microtime(true);
		recBinarySearch($array, $value, $low, $high);
		$end = microtime(true);
		
		$timeElapsed += ($end - $start);
		$count++;
	}
	
	echo $count;
}

function repetitiveSearch($repetitions = 10000) {
	$file = fopen('log.txt', 'w+'); // Save into .csv to open Excel
	//fwrite($file, "#\tRec. binary search\tIter. binary search\tSuccess" . PHP_EOL);
	$runs = 1;
	while ($repetitions > 0) {
		$array = generateRandomArray();
		$low = 0;
		$high = count($array)-1;
		$value = mt_rand(0, 4095);
		
		$start = microtime(true);
		$result = recBinarySearch($array, $value, $low, $high);
		$end = microtime(true);
		
		$success = 'Found';
		if (!$result) {
			$success = 'Not found';
		}
		$recTime = $end-$start;

		$start = microtime(true);
		$result = iterBinarySearch($array, $value);
		$end = microtime(true);
		
		$iterTime = $end-$start;
		
		//fputcsv($file, array($runs, $recTime, $iterTime, $success));
		fwrite($file, $runs . "\t" . $recTime . "\t" . $iterTime . "\t" . $success . PHP_EOL);
		$repetitions--;
		$runs++;
	}
	fclose($file);
}

function recBinarySearch(array $array, $value, $low, $high) {
	if ($high < $low) {
		return false;
	}
	
	$middle = floor($low + (($high - $low)/2));

	if ($array[$middle] > $value) {
		return recBinarySearch($array, $value, $low, $middle-1);
	} else if ($array[$middle] < $value) {
		return recBinarySearch($array, $value, $middle+1, $high);
	} else {
		return $middle;
	}
}

function iterBinarySearch(array $array, $value) {
	$low = 0;
	$high = count($array)-1;
	
	while ($low <= $high) {
		$middle = (int)($low + (($high - $low)/2));
		
		if ($array[$middle] > $value) {
			$high = $middle-1;
		} else if ($array[$middle] < $value) {
			$low = $middle+1;
		} else {
			
			return $middle;
		}
	}

	return false;
}

function insertArrayIntoFile($fileName, array $array) {
	$file = fopen($fileName, 'w+');
	$size = count($array);
	foreach ($array as $i => $key) {
		$eol = PHP_EOL;
		if ($i == ($size-1)) {
			$eol = '';
		}
		fwrite($file, $key . $eol);
	} 
	fclose($file);
}

function readArrayFromFile($fileName) {
	$array = explode(PHP_EOL, file_get_contents($fileName));
	
	return $array;
}

function generateRandomArray($size = 1000, $max = 4095, $sort = true) {
	$array = array();
	
	while($size > 0) {
		$array[] = mt_rand(1, $max);
		$size--;
	}
	
	if ($sort) {
		sort($array);
	}
	
	return $array ;
}